package com.zhj.algorithm.sort;

import java.util.Arrays;

/**
 * @PackageName:com.zhj.algorithm.sort
 * @ClassName:RadixSort
 * @auter: 朱慧杰
 * @date:2020/8/9 0009 18:57
 **/
public class RadixSortByQueue {

    // 基数排序
    public static void main(String[] args) {
        int[] arr = new int[]{23,6,189,45,9,287,56,1,789,34,65,652,5};
        System.out.println(Arrays.toString(arr));
        radixSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void radixSort(int[] arr) {
        // 存数组中最大数字
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
        System.out.println("数组中最大数值为: " + max);
        // 计算这个最大数字 是几位数
        int maxLength = (max + "").length();
        System.out.println("数组中最大数字为 " + maxLength + " 位数");

        // 用于零时存数据的数组  ----队列
        MyQueue[] temp = new MyQueue[10];
        for (int i = 0; i < temp.length; i++) {
            temp[i] = new MyQueue();
        }

        for (int i = 0,n = 1; i < maxLength; i++,n*=10) {
            for (int j = 0; j < arr.length; j++) {
                // 每一位最后一个数
                int ys = arr[j]/n%10;
                temp[ys].add(arr[j]);
            }
            // 记录取出元素需要放到的位置
            int index = 0;
            for (int j = 0; j < temp.length; j++) {
                if (temp[j] != null) {
                    while (!temp[j].isEmpty()) {
                        arr[index] = temp[j].poll();
                        index++;
                    }
                }
            }

        }

    }

}
